package com.yang.Dp.bags.ComBages;

/**
 * @Author: yang
 * @Description:
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
 * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
 * 假设每一种面额的硬币有无限个。
 * 题目数据保证结果符合 32 位带符号整数。
 * @Date: Created in 14:56 2022/8/11
 * @Modified By:
 */
public class LeetCode518 {
    public static void main(String[] args) {
        LeetCode518Solution leetCode518Solution = new LeetCode518Solution();
        int[] nums = {1, 2, 3, 4, 5};
        leetCode518Solution.change(6, nums);
    }
}
class LeetCode518Solution {
    public int change(int amount, int[] coins) {
        // 1.dp[j] 表示对应总金额j 有dp[j] 中凑齐方式
        // 2.dp[j] = Math.max(dp[j], dp[j - coins[i]] + 1);
        // 3.初始化方式 对应dp[0] = 1; 理解为装满容量0 有一种方法
        // 4.循环方式 因为可以重复货币 那么就是从小到大遍历、
        // 对于先循环物品 这种遍历顺序中dp[j]里计算的是组合数
        // 先循环容量 算出来的就是排列数
        int dp[] = new int[amount + 1];
        dp[0] = 1;

        // 外层物品
        for(int i  = 0; i < coins.length; i++){
            System.out.println(" i:" + i + " ");
            // 内层容量
            for(int j = 1; j <= amount; j++){
                if(j < coins[i]) continue;
                dp[j] += dp[j - coins[i]];
                System.out.println("dp[" + j + "]: "+ dp[j]);
            }
        }
        return dp[amount];
    }
}
